home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.mactech.com 2010
/
ftp.mactech.com.tar
/
ftp.mactech.com
/
machack
/
Hacks97
/
WarriorsProgress.sit
/
Warrior’s Progress
/
source code
/
Source
/
Libraries
/
Trees
/
RedBlackNode.cp
< prev
next >
Wrap
Text File
|
1997-06-28
|
2KB
|
143 lines
// RedBlackNode.cp
#ifndef RedBlackNode_h
#include "RedBlackNode.h"
#endif
#ifndef RedBlackTree_h
#include "RedBlackTree.h"
#endif
#ifndef Swap_h
#include "Swap.h"
#endif
RedBlackNode::RedBlackNode()
: red( true )
{
}
RedBlackNode::~RedBlackNode()
{
if ( Owned() )
Owner().Remove( *this );
}
RedBlackTree& RedBlackNode::DownCast( Tree& n )
{
return static_cast< RedBlackTree& >( n );
}
const RedBlackTree& RedBlackNode::DownCast( const Tree& n )
{
return static_cast< const RedBlackTree& >( n );
}
uint32 RedBlackNode::RedChildren() const
{
return ( HasLeftChild() ? Left()->red : 0 )
+( HasRightChild() ? Right()->red : 0 );
}
void RedBlackNode::SwapWith( RedBlackNode& partner )
{
Swap( red, partner.red );
TreeNode::SwapWith( partner );
}
void RedBlackNode::RotateUp()
{
Assert( !IsRoot() );
if ( IsBlack() )
{
if ( IsLeftChild() )
{
Assert( Parent()->HasRightChild() );
Assert( Parent()->Right()->IsBlack() );
Parent()->Right()->red = true;
Assert( HasLeftChild() );
Assert( Left()->IsRed() );
Left()->red = false;
}
else
{
Assert( IsRightChild() );
Assert( Parent()->HasLeftChild() );
Assert( Parent()->Left()->IsBlack() );
Parent()->Left()->red = true;
Assert( HasRightChild() );
Assert( Right()->IsRed() );
Right()->red = false;
}
}
Swap( red, Parent()->red );
TreeNode::RotateUp();
}
void RedBlackNode::Raise()
{
Assert( IsBlack() );
Assert( RedChildren() == 2 );
red = true;
Left()->red = false;
Right()->red = false;
}
void RedBlackNode::Lower()
{
Assert( IsRed() );
Assert( HasLeftChild() );
Assert( HasRightChild() );
Assert( Left()->IsBlack() );
Assert( Right()->IsBlack() );
red = false;
Left()->red = true;
Right()->red = true;
}
bool RedBlackNode::Valid( uint32 blackHeight ) const
{
if ( !TreeNode::Valid() )
return false;
if ( red && !IsRoot() && Parent()->red )
return false;
if ( IsBlack() )
{
if ( blackHeight == 0 )
return false;
blackHeight--;
}
if ( Left() == 0 )
{
if ( blackHeight > 0 )
return false;
}
else
{
if ( !Left()->Valid( blackHeight ) )
return false;
}
if ( Right() == 0 )
{
if ( blackHeight > 0 )
return false;
}
else
{
if ( !Right()->Valid( blackHeight ) )
return false;
}
return true;
}